Fu dell' Imperatrice Maria Alexandrovna l’idea di edificare una Chiesa russa all’inizio del viale a lei dedicato; nel 1890 il granduca Sergeij Michailovich, anch’egli residente a Sanremo, sostenne con forza il progetto. Sarà proprio il granduca a presiedere, nel 1910, il comitato per la costruzione della Chiesa, costituito con un decreto speciale dell’Imperatore Nicola II, che non si limitò ad autorizzare la raccolta di fondi per l’edificazione del tempio, ma fu uno dei principali benefattori e donatori. Il conte Cheremetiev, residente a Sanremo, fu nominato presidente del comitato. Tra i membri del comitato va ricordato l’architetto Alexeij Viktorovič Čtchoussev, che contribuì al progetto della chiesa. Čtchoussev non si recò mai a Sanremo e i lavori vennero diretti da un architetto locale, Pietro Agosti, cui fu dedicata una via della città ligure.
Il tempio poggia su fondamenta di cemento armato, è costruito in mattoni ed è sormontato da cinque cupole a bulbo. La forma è cubica, e la struttura dell’edificio è conforme allo stile delle chiese moscovite del XVII secolo, con le caratteristiche decorazioni dei kokočniki. La sommità delle pareti esterne è di forma semicircolare; questo dettaglio assicura una transizione armoniosa dalle forme squadrate delle pareti stesse alle cupole tondeggianti. Queste, sormontate da croci in stile russo, sono ricoperte di scaglie multicolori, che donano un aspetto luminoso e gioioso all’edificio. Sempre in stile moscovita, la torre campanaria è sormontata da un piccolo bulbo.
In contrasto con le ricche decorazioni esterne, l’interno della chiesa appare piuttosto sobrio. Il tempio infatti non è affrescato, e la principale decorazione è costituita dalla splendida iconostasi. Per la realizzazione delle icone di Cristo e della Madonna, furono commissionate copie di due famose opere realizzate rispettivamente da Michail Vrubel per la Chiesa di San Cirillo a Kiev, e da Victor Vasnetsov per la Cattedrale di San Vladimiro, nella stessa città. Nel nartece della Chiesa è inoltre conservata una splendida tavola che riproduce il grande affresco absidale della Cattedrale di San Vladimiro a Kiev, raffigurante la Vergine Maria che regge l'Emanuele. L'opera originale è di Victor Vasnetsov. Conformemente alla tradizione, l'iconostasi fu concepita per contenere le icone dei santi protettori della chiesa, Caterina di Alessandria e Serafino di Sarov. Queste tavole furono rimosse nel 1974 e collocate sulle pareti del tempio; al loro posto furono collocate le icone degli arcangeli Michele e Gabriele, opere dell'iconografo Tsevčinskij.
In tempi recenti la chiesa è stata arricchita da molte pregevoli opere dell'iconografo Alexander Moltchanov. Sulle pareti sono inoltre presenti le icone delle sante Xenia e Vera, provenienti dalla cripta della chiesa: si trovavano in corrispondenza delle tombe delle principesse Xenia e Vera del Montenegro, sepolte assieme ai genitori, Nicola e Milena del Montenegro. Il re Nicola I del Montenegro conformemente alle sue ultime volontà fu tumulato nella cripta della piccola chiesa russa di Sanremo. Nell'anno 1989, i resti della famiglia reale montenegrina furono trasferiti a Cettigne, ex capitale del Montenegro. Delle sepolture reali restano nella cripta solo i sarcofaghi, in marmo nero, opera dell'architetto Guidiccini. Davanti alla chiesa sono inoltre collocati i busti del re d'Italia Vittorio Emanuele III e di sua moglie, Elena del Montenegro, figlia di Nicola I.
Più vicino ai giorni nostri, precisamente nel 1940, una bomba, lanciata da un aereo, cadde sull’edificio e sfondò il pavimento; i parrocchiani riempirono la chiesa di sacchetti di sabbia e continuarono a celebrare la liturgia nella cripta e nella cappella del cimitero della Foce. La situazione della chiesa fu complicata ulteriormente da una causa giudiziaria, che nel 1953 il conte Vittorio Tallevici intentò contro il comitato della Chiesa Russa: egli pretendeva la restituzione del denaro prestato a suo tempo per l’edificazione del tempio. Il processo durò tredici anni e si concluse a favore della comunità: si riuscì infatti a dimostrare che il conte, avendo ottenuto dei redditi dalla chiesa, dal terreno e dalla casa annessa, già da molto tempo era rientrato in possesso della somma prestata.
Nel 1961, dopo un restauro di manutenzione eseguito a spese del Comune di Sanremo, la chiesa fu dichiarata monumento d’arte. La fama crescente del monumento e le difficoltà in cui versava la comunità russa diedero luogo a numerosi tentativi da parte del Comune di acquistare la chiesa per allestirvi un museo, una biblioteca o altro: tentativi mai riusciti.
Nell’estate del 1990 è stata collocata nel nartece una lapide di marmo che riassume la storia della costruzione e della conservazione della chiesa.